package com.ease.context.algorithm;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.ease.common.util.Detect;
import com.ease.context.datastructure.TreeNode;

/**
 * 
 * @author nathanleewei
 * 
 */
public abstract class Trees extends Detect {

	/**
	 * Breadth First Search
	 * 
	 * @param <T>
	 * @param root
	 * @param callback
	 */
	public static <T extends TreeNode<T>> void breadthFirstSearch(T root, TreeNodeVisitCallback<T> callback) {
		if (null != root) {
			Queue<T> queue = new LinkedList<T>();
			queue.add(root);

			while (!queue.isEmpty()) {
				T treeNode = queue.poll();
				callback.visit(treeNode);
				List<T> children = treeNode.children();
				if (notEmpty(children)) {
					for (T child : children) {
						queue.add(child);
					}
				}
			}
		}
	}

	/**
	 * Depth First Search. It is variant, visit rootNode first.
	 * 
	 * @param <T>
	 * @param treeNode
	 * @param callback
	 */
	public static <T extends TreeNode<T>> void depthFirstSearch(T treeNode, TreeNodeVisitCallback<T> callback) {
		if (null != treeNode) {
			callback.visit(treeNode);
			List<T> children = treeNode.children();
			if (notEmpty(children)) {
				for (T child : children) {
					depthFirstSearch(child, callback);
				}
			}
			// callback.visit(treeNode);The standard DFS
		}
	}

}
